// https://leetcode.cn/problems/bLyHh0/

// 题干：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
//省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
//给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
//返回矩阵中 省份 的数量。

// 示例：输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
//      输出：2

// 碎语：并查集的实战

#include <bits/stdc++.h>
using namespace std;

class UnionFindSet
{
public:
    // 初始时，将数组中元素全部设置为-1
    UnionFindSet(size_t n)
            :_ufs(n, -1)
    {}

    // 给一个元素的编号，找到该元素所在集合的名称
    void Union(int x1, int x2)
    {
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);

        // 如果本身就在一个集合，那么无需合并
        if (root1 == root2) return ;

        // 如果有需求下标小的作根，则交换一下root
//        if (root1 > root2) swap(root1, root2);

        // 如果不在同一个集合，则默认认为把x2代表集合合并到x1上，即x1作根，x2作子
        _ufs[root1] += _ufs[root2];

        // 将x2代表集合的名称改为x1
        _ufs[root2] = root1;
    }

    // 给一个元素的编号，找到该元素所在集合的名称
    int FindRoot(int x)
    {
        int parent = x;
        while (_ufs[parent] >= 0){
            parent = _ufs[parent];
        }

        return parent;
    }

    bool isInset(int x1, int x2) // 是不是在同一个集合
    {
        return FindRoot(x1) == FindRoot(x2);
    }

    size_t SetSize() // 计算一下有几个集合（树）
    {
        size_t size = 0;
        for (size_t i = 0 ; i < _ufs.size() ; i++){
            if (_ufs[i] < 0) size++;
        }

        return size;
    }
private:
    vector<int> _ufs; // 假设给的就是下标
};

class Solution
{
public:
    int findCircleNum(vector<vector<int>>& isConnected)
    {
        UnionFindSet ufs(isConnected.size());

        for (size_t i = 0 ; i < isConnected.size() ; i++){
            for (size_t j = 0 ; j < isConnected[i].size() ; j++){
                if (isConnected[i][j]){
                    ufs.Union(i, j);
                }
            }
        }

        return ufs.SetSize();
    }

};

int main()
{
    Solution sol;

    vector<vector<int>> isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
    cout << sol.findCircleNum(isConnected) << endl;

    return 0;
}